#include <stdio.h>
#include <stdlib.h>
#define NAMESIZE 2
#define MAPSIZE 16
//Construct a MapLib Structure, including:
struct MapLib{ 
	int mapsize; // size of map;
	char landname[MAPSIZE][NAMESIZE]; // names of lands on the map such as CA LA or NY;
	int matrix[MAPSIZE][MAPSIZE]; // the matrix indicating the boundaries between lands;
	int color[MAPSIZE]; //the series indicating the color of each land with specific num.
	};
typedef struct MapLib *PMapLib;
//Detecting whether the coloring is finished.
int isFinish(PMapLib sample) { 
	int i = 0;
	while (i<sample->mapsize) {
		if (sample->color[i]==0) {
			return 0;
			}
		i++;
		}
	return 1;
	}
//Detecting whether the num land can be colored with "color";	
int notAdjWith (int color, PMapLib sample, int num) {  
	int i = 0;
	while (i<sample->mapsize) {
			if (sample->color[i]==color) { //of current color
				if (sample->matrix[num][i]==1) { //if it is adjacent to current land.
					return 0;
					}
				}
		i++;
		}
	return 1;
	}
//To color up the sample map, return the num of colors that were used.
int colorUp (PMapLib sample) {
	int color = 0;
	while (!isFinish(sample)) {
		color++;
		int i=0;
		for (i=0;i<sample->mapsize;i++) {
			if (notAdjWith(color, sample, i)&&sample->color[i]==0) { 
				sample->color[i]=color;  //If no adjacent-same-color land found, then color it.
				}
			}
	}
	return color;  //detecting if all the land are colored.
	}	
//To generate the map, from "landlist.dat" with land names,
//and "matrix.dat" with boundary matrix.
PMapLib generateMap (int mapsize) {
	int i=0,j=0;
	PMapLib map=(PMapLib)malloc(sizeof(struct MapLib));
	map->mapsize=mapsize;
	
	FILE *fr;
	FILE *fr_m;
	fr = fopen("landlist.dat","rt");
	fr_m = fopen("matrix.dat","rt");
	
	char landlist[MAPSIZE][NAMESIZE];
	int matrix[MAPSIZE][MAPSIZE];
	char separate;
//Firstly, the data are put into 	"landlist" and "matrix".
//Input file contains lands' name separated by one byte.
	for(i=0;i<mapsize&&separate!=EOF;i++) {   
  	for (j=0;j<NAMESIZE;j++) {
  		landlist[i][j]=fgetc(fr);
  		}
 		separate=fgetc(fr);
  	}
	for(i=0;i<mapsize;i++) {
  	for (j=0;j<mapsize;j++) {
  		matrix[i][j]=0; //Initialization of the matrix
  		}
  	}
	for(i=0;i<mapsize;i++) {
  	for (j=0;j<=i;j++) {
  		matrix[i][j]=fgetc(fr_m)-'0';
 			matrix[j][i]=matrix[i][j]; //One can just input lower left half of the matrix.
  		}
 	char temp=fgetc(fr_m);	
 	if (temp=='\n') continue;
  	}
  	
	for(i=0;i<mapsize;i++) {
  	for (j=0;j<NAMESIZE;j++) {
  		map->landname[i][j]=landlist[i][j]; //Transfer names from landlist to sample map.
  		}
  	map->color[i]=0;        //Initial color should be 0.
  	}
  	
	for(i=0;i<mapsize;i++) {
  	for (j=0;j<i;j++) {
  		if (matrix[i][j]!=0&&matrix[i][j]!=1) {
  			printf ("Illegal matrix input.");
  			}//report the error if the element of matrix is not 1 or 0.
  		map->matrix[i][j]=matrix[i][j];//Transfer elements from matrix to sample map matrix.
  		map->matrix[j][i]=matrix[i][j]; 
  		}
  	}
  	return map;
	}
//Function to output the color result.	
int outputColoredMap (PMapLib sample) {
	int i,j,color;
	int colornum=colorUp(sample);
	printf("\n%d colors used.",colornum);
	for (color=1;color<=colornum;color++) {
		printf("\nColor %d: ",color);
		for (i=0;i<sample->mapsize;i++) {
			if(sample->color[i]==color) {
				for (j=0;j<NAMESIZE;j++) {
					printf("%c",sample->landname[i][j]);
					}
				printf(" ");
				}
			}
		}
	printf("\n");
	}

int main()
{
	PMapLib map;
	int mapsize=16; 
	map = generateMap(mapsize);
	int i,j;
	
    for(i=0;i<mapsize;i++) {   //Input file contains the matrix.
  	for (j=0;j<mapsize;j++) {
  		printf("%d",map->matrix[i][j]);
  		}
  		printf("\n");
  	}
   
   outputColoredMap(map);
   
  	
  system("PAUSE");	
  return 0;
}

